package Sort;

import java.util.Arrays;

/**
 * @Author Fizz Pu
 * @Date 2021/3/12 下午4:50
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 快速排序: 非稳定排序 主元  原地排序 最好的时间复杂度是O(nlgn) 空间复杂度: O(lgn);
// 适用场景: 数比较多而且无序

// 优化
// 主元的选取
// 当数目比较少的时候, 选用插入排序

/**
 * 6 4 5 9
 *   i   j
 *   找一个大于pivot的元素
 */

public class QuickSort implements SortAlgrithom {
    public static void main(String[] args) {
        int[] data = new int[]{
                1,2,3,1,1
        };
        new QuickSort().quickSort(data, 0, 4);
        System.out.println(Arrays.toString(data));
    }

    private void quickSort(int[] arr, int left, int right) {
        if(left < right){
            int partition = partion(arr, left, right);
            quickSort(arr, left, partition - 1);
            quickSort(arr, partition + 1, right);
        }
    }

    @Override
    public void sort(int[] arr) {
        long start = System.currentTimeMillis();
        if(arr == null){
            throw  new IllegalArgumentException();
        }

        int len = arr.length;
        quickSort(arr, 0, len - 1);
        System.out.println(Arrays.toString(arr));
        long end = System.currentTimeMillis();
        long cost = end - start;
        System.out.println(Arrays.toString(arr) + "排序耗时: " + cost);
    }

    // 1. 选取任意一个元素作为主元
    // 2. 定义一个左指针, 从左往右找一个大于主元的元素
    // 3. 定义一个右指针, 从右往左找一个小于主元的元素
    // 4. 当两指针重合时退出, 否则转5
    // 5. 交换左右指针对应的元素
    // 6. 循环推出后主要放到该放的位置上, 即主元和右边指针交换

    private int partion(int[] arr, int left, int right){
        int pivot = arr[left];
        int i = left + 1;
        int j = right;

        while (true){
            // 找一个大于主元的元素
            while (i <= j && arr[i] <= pivot){
                i++;
            }

            // 找一个小于主元的元素
            while (i <= j && arr[j] >= pivot){
                j--;
            }

            if(i >= j){
                break;
            }

            // 交换
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 复位
        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
}
